package com.JAVA程序员面试宝典;

/**
 * 求素数
 * 筛选法
 * @author qiuxiaochen
 *
 */
public class 求素数 {

	public void process(int num) {
		int a[] = new int[num + 1];
		//首先将所有标记为1
		for (int i = 0; i < a.length; i++) {
			a[i] = 1;
		}
		for (int i = 2; i < a.length; i++) {
			//如果标记为1的话，经过第一轮标记，4已经以2的倍数的身份被标记为0
			if (a[i] == 1) {
				//将所有数字i的倍数的数字都标记为0
				for (int j = i + i; j < a.length;) {
					if (j % i == 0) {
						a[j] = 0;
						j = j + i;
					}
				}
			}
		}
		for (int i = 1; i < a.length; i++) {
			if (a[i] == 1)
				System.out.println(i);
		}
	}

	public static void main(String[] args) {
		new 求素数().process(100);
	}
}
